/*
 *      Author : Pallab
 *      Prog: E.cxx
 *
 *      Created on: 02:54:57 AM - 2013:2:23
 * "I have not failed, I have just found 10000 ways that won't work."
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;


#define foR(i,frm,upto) for( int i=(frm),_i=(upto);(i) < (_i) ; ++i )
#define foD(i,frm,upto) for( int i=(frm),_i=(upto);(i) >= (_i) ; --i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define dbg(...)       printf(__VA_ARGS__)
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait ( double seconds ) {
    double endtime = clock() + ( seconds * CLOCKS_PER_SEC );
    while ( clock() < endtime ) {
        ;
    }
}
template<class T>
    inline T fastIn() {
    register char c=0;
    register T a=0;
    bool neg=false;
    while ( c<33 ) c=getchar();
    while ( c>33 ) {
        if ( c=='-' ) {
            neg=true;
        } else {
            a= ( a*10 ) + ( c-'0' );
        }
        c=getchar();
    }
    return neg?-a:a;
}
template<class T>
    inline int bc ( T msk ) {
    int c=0;
    for ( c=0; msk>0 ; ++c ) {
        msk&= ( msk-1 );
    }
    return c;
}
template<class T1, class T2>
        inline T1 OR ( T1 msk,T2 bit ) {
        return ( msk| ( 1<<bit ) );
    }
template<class T1, class T2>
        inline T1 AND ( T1 msk, T2 bit ) {
        return ( msk& ( 1<<bit ) );
    }
template<class T1, class T2>
        inline T1 Clear ( T1 msk, T2 bit ) {
        return ( msk& ( ~ ( 1<<bit ) ) );
    }
template<class T1, class T2>
        inline bool marked ( T1 msk, T2 bit ) {
        return ( AND ( msk,bit ) !=0 );
    }
int N,K;
inline void read() {
    N=fastIn<int>(),K=fastIn<int>();
}
inline bool isPalin ( int const &number, int const &length ) {
    for ( int i=0,j=length-1; i<=j; ++i,--j ) {
        bool f1 = number& ( 1<<i ),f2 = number& ( 1<<j );
        if ( f1!=f2 ) return false;
    }
    return true;
}

Int const module=1000000007LL;
inline Int domod ( Int number ) {
    number = number%module;
    if ( number<0 ) number+=module;
    return number;
}
Int dp[401][ ( 1<<10 ) ];
Int go ( int at, int msk ) {
    if ( at>=K && isPalin ( msk,K ) ) return 0LL;
    if ( at>=N ) return 1LL;

    Int &d=dp[at][msk];
    if ( d!=-1 ) return d;
    d=0LL;
    msk = ( ( msk<<1 ) & ( ~ ( 1<<K ) ) );
    int nmsk1 = ( msk );
    int nmsk2 = ( msk ) | ( 1 );
    d=domod ( d+go ( at+1,nmsk1 ) );
    d=domod ( d+go ( at+1,nmsk2 ) );
    return d;
}

inline void proc() {
    SET ( dp,-1 );
    Int retval=go ( 0,0 );
    cout<<retval<<"\n";
}
int main() {
    int kase = 1;
#if defined( xerxes_pc )
    if ( !freopen ( "in1", "r", stdin ) )
        puts ( "error opening file in " ), assert ( 0 );
    kase = 1;
#endif
    kase=fastIn<int>();
    foR ( i,0,kase ) {
        read();
        proc();
    }
    return 0;
}
// kate: indent-mode cstyle; indent-width 4; replace-tabs on; 

